package ru.mersenn;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Date;

import org.apache.commons.math3.complex.Complex;
import org.apache.commons.math3.transform.DftNormalization;
import org.apache.commons.math3.transform.FastFourierTransformer;
import org.apache.commons.math3.transform.TransformType;
import org.apache.log4j.BasicConfigurator;
import org.apache.log4j.Logger;

/**
 * до 10^8 всего 5 761 455 простых чисел до 32го числа 1 622 440 простых, те
 * надо проверить 4 * 10 ^ 6 чисел
 * 
 * @author akargapolov
 * @since 13.02.2013
 */
public class Mersenn
{
	static final Logger log = Logger.getLogger("mersenn");

	public static void main(String[] args)
	{
		BasicConfigurator.configure();
		log.info("start");

//		checkSieve(50000);
		// sieve();
		// checkFft();

		int[] tests =
		// {3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203,
		// 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209};
		// 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787,
		// 1398269, 2976221, 3021377, 6972593, 13466917, 20996011,
		// 24036583 };
		{ 13 };
		// {7};
		for (int q : tests)
		{
			// checkPrime(q);
			checkPrimeFFT(q);
		}
	}

	private static void checkFft()
	{
		/*
		 * Complex[] a1 = { Complex.valueOf(2), Complex.valueOf(12318),
		 * Complex.valueOf(12352), Complex.valueOf(23423),
		 * Complex.valueOf(34563), Complex.valueOf(78322),
		 * Complex.valueOf(23131), Complex.valueOf(2) };
		 */

		double[] a1 =
		{ 2, 2, 2, 2, 0, 0, 0, 0 };// надо дополнять нулями!!!

		// double[] a1 = { 4, 3, 2, 1, 0, 0, 0, 0 };

		long[] a2 = new long[a1.length];
		Complex[] cmx = fft.transform(a1, TransformType.FORWARD);
		log.info(Arrays.toString(cmx));
		for (int i = 0; i < cmx.length; ++i)
		{
			cmx[i] = cmx[i].multiply(cmx[i]);
		}
		log.info(Arrays.toString(cmx));
		cmx = fft.transform(cmx, TransformType.INVERSE);
		log.info(Arrays.toString(cmx));

		for (int i = 0; i < cmx.length; ++i)
		{
			a2[i] = (long) (cmx[i].getReal() + 0.5);
		}

		log.info(Arrays.toString(a1));
		log.info(Arrays.toString(a2));
	}

	static FastFourierTransformer fft = new FastFourierTransformer(
			DftNormalization.STANDARD);

	/**
	 * Проверяет быстро для 10^4 9941 - 3 сек 44497 - 5 мин
	 */
	private static void checkPrime(int q)
	{
		Date start = new Date();
		BigInteger m = new BigInteger("2").pow(q).subtract(BigInteger.ONE);
		BigInteger l = new BigInteger("4");

		for (int i = 1; i <= q - 2; ++i)
		{
			if (i % 10000 == 0)
			{
				log.info(i);
			}

			l = l.pow(2).subtract(BigInteger.valueOf(2)).mod(m);
		}

		log.info((l.equals(BigInteger.ZERO) ? "" : " not") + "prime q = " + q
				+ ", Mq = " + m);

		log.info("time " + (new Date().getTime() - start.getTime()) + "ms");
	}

	private static void checkPrimeFFT(int q)
	{
		Date start = new Date();
		boolean isPrime = new MersennSeq(q).isPrime();
		log.info((isPrime ? "" : "not ") + "prime q = " + q);
		log.info("time " + (new Date().getTime() - start.getTime()) + "ms");
	}

	private static ArrayList<Integer> sieve(int size)
	{
		Date start = new Date();
		boolean[] flag = new boolean[size];
		ArrayList<Integer> res = new ArrayList<Integer>();
		Arrays.fill(flag, true);
		int count = 0;

		for (int i = 2; i < size; ++i)
		{
			if (flag[i])
			{
				log.info(i);
				++count;
				res.add(i);
				for (int j = i + i; j < size; j += i)
					flag[j] = false;
			}
		}
		log.info("sieve " + size + " time "
				+ (new Date().getTime() - start.getTime()) + "ms");
		log.info("all " + count);
		return res;
	}

	/**
	 * всего 5% отсеивается
	 * @param size
	 */
	private static void checkSieve(int size)
	{
		ArrayList<Integer> primes = sieve(size);
		
		int i,j;
		
		int count = 0;
		for (i = 100;i<primes.size();++i)
		{
			int q = primes.get(i);
			for (j = 0;j<primes.size();++j)
			{
				int m = primes.get(j);
				BigInteger t = new BigInteger("2").modPow(BigInteger.valueOf(q), BigInteger.valueOf(m));
				t = t.add(BigInteger.valueOf(m - 1)).mod(BigInteger.valueOf(m));
				if (t.equals(BigInteger.ZERO))
				{
					count++;
					break;
				}
			}
		}
		
		log.info("all - " + primes.size() + " primes - " + count);
	}
}
